package toOffer;

/**
 * <h3>leetcode</h3>
 *
 * @author BigFaceCat
 * @date 2024/1/24 9:40
 * @description <p>不含重复字符的最长子字符串 </p>
 */

import java.util.HashMap;
import java.util.Map;
import java.util.Objects;

/**
 * 题目：输入一个字符串，求该字符串中不含重复字符的最长子字符串
 * 的长度。例如，输入字符串"babcca"，其最长的不含重复字符的子字符串是
 * "abc"，长度为 3。
 */
public class toOffer3_2_16 {
    public static void main(String[] args) {
        String s = "pwasf1255";
        System.out.println(lengthOfLongestSubstring(s));

    }

    /**
     * 双指针，左指针指向移动子字符串的第一个数，右指针指向最后一个数
     * 如果右指针右移，这个子字符串不重复，那么记录这个数（右指针-左指针）、继续右移；
     * 如果重复，那么让左字符串右移、直到子字符串不重复
     *
     * @param s
     * @return
     */
    public static int lengthOfLongestSubstring(String s) {
        //判空
        if (Objects.isNull(s) || s.length() == 0) {
            return 0;
        }

        int result = 1;
        int slow = 0;
        int fast = 1;
        //初始化map
        Map<Character, Integer> map = new HashMap<>();
        map.put(s.charAt(0), 1);

        while (fast < s.length()) {
            //不管左指针怎么移、右指针每次都移动一位
            map.put(s.charAt(fast), map.getOrDefault(s.charAt(fast), 0) + 1);
            fast++;
            //map里存在重复值的话，就让左指针右移
            if (!judge(map)) {
                map.put(s.charAt(slow), map.get(s.charAt(slow)) - 1);
                slow++;
            }
            result = Math.max(result, fast - slow);
        }
        return result;
    }

    /**
     * map里的v只要有一个大于1、就返回false
     *
     * @param newMap
     * @return
     */
    public static boolean judge(Map<Character, Integer> newMap) {
        for (Character key : newMap.keySet()) {
            if (newMap.get(key) > 1) {
                return false;
            }
        }
        return true;
    }
}
